from numpy import *  
import time  
  
# calculate Euclidean distance  
def euclDistance(vector1, vector2):  
    return sqrt(sum(power(vector2 - vector1, 2)))  
  
# init centroids with random samples  
def initCentroids(dataSet, k):  
    numSamples, dim = dataSet.shape
    #print numSamples,dim  
    centroids = zeros((k, dim))  
    for i in range(k):  
        index = int(random.uniform(0, numSamples))  
        centroids[i, :] = dataSet[index, :]  
    return centroids  
  
# k-means cluster  
def kmeans(dataSet, k):  
    numSamples = dataSet.shape[0]  
    # first column stores which cluster this sample belongs to,  
    # second column stores the eucl between this sample and its centroid  
    clusterAssment = mat(zeros((numSamples, 2)))  
    clusterChanged = True  
  
    ##init centroids  
    centroids = initCentroids(dataSet, k)  
  
    while clusterChanged:  
        clusterChanged = False  
        ## for each sample  
        for i in xrange(numSamples):  
            minDist  = 100000.0  
            minIndex = 0  
            ## for each centroid  
            ## ind the centroid who is closest  
            for j in range(k):  
                distance = euclDistance(centroids[j, :], dataSet[i, :])  
                if distance < minDist:  
                    minDist  = distance  
                    minIndex = j  
              
            ##update its cluster  
            if clusterAssment[i, 0] != minIndex:  
                clusterChanged = True  
                clusterAssment[i, :] = minIndex, minDist**2  
  
        ## update centroids  
        for j in range(k):  
            pointsInCluster = dataSet[nonzero(clusterAssment[:, 0].A == j)[0]]  
            centroids[j, :] = mean(pointsInCluster, axis = 0)  
  
   ##cluster complete  
    #print centroids
    #print clusterAssment
    return centroids, clusterAssment

def runfromfile(dir,k=2):
    ## load data  
    dataSet = []  
    fileIn = open(dir)  
    for line in fileIn.readlines():  
        dataSet.append(float(line)) 
      
    ## clustering...   
    dataSet = mat(dataSet).T
    #print dataSet  
    #k = 2  
    centroids, clusterAssment = kmeans(dataSet, k)
    return clusterAssment

def run(dataSet,k = 2):
    #print "----------------------run kmeans------------------\n"
    #dataSet = rttDiff.testdiff()
    dataSet = mat(dataSet).T
    #print dataSet  
    #k = 2  
    centroids, clusterAssment = kmeans(dataSet, k)
    return clusterAssment

if __name__ == "__main__":
    runfromfile('/home/zxg/scandir/sandwichlog.txt',2)
'''
if __name__ == "__main__":
    ## load data  
    dataSet = []  
    fileIn = open('/home/zxg/scandir/log.txt')  
    for line in fileIn.readlines():  
        dataSet.append(float(line)) 
      
    ## clustering...   
    dataSet = mat(dataSet).T
    #print dataSet  
    k = 2  
    centroids, clusterAssment = kmeans(dataSet, k)
'''  
